package practice;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/27 14:44
 */
public class KMP {
    public static int indexOf(String text, String pattern) {
        if (text == null || pattern == null) return -1;
        char[] t = text.toCharArray();
        int tlen = t.length;
        if (tlen == 0) return -1;
        char[] p = pattern.toCharArray();
        int plen = p.length;
        if (plen == 0) return -1;

        int[] next = next(pattern);

        int pi = 0;
        int ti = 0;
        int delta = tlen - plen;
        while (pi < plen && ti - pi <= delta) {
            if (pi < 0 || p[pi] == t[ti]) {
                pi++;
                ti++;
            } else {
                pi = next[pi];
            }
        }
        return (pi == plen) ? (ti - pi) : -1;
    }

    private static int[] next(String pattern) {
        char[] p = pattern.toCharArray();
        int[] next = new int[p.length];
        int n = next[0] = -1;
        int i = 0;
        int imax = p.length - 1;
        while (i < imax) {
            if (n < 0 || p[i] == p[n]) {
                i++;
                n++;
                if (p[i] == p[n]) {
                    next[i] = next[n];
                } else {
                    next[i] = n;
                }
            } else {
                n = next[n];
            }
        }
        return next;
    }
}
